import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:滑动窗口
 * User: LianBao
 * Date: 2024-06-08
 * Time: 18:51
 */
public class Main {
    /**
     * 1. 长度最小的子数组
     * https://leetcode.cn/problems/minimum-size-subarray-sum/description/
     *
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {

        int left = 0, right = 0;
        int sum = 0;
        int len = Integer.MAX_VALUE;
        while (right < nums.length) {
            sum += nums[right];//进窗口
            //判断
            while (sum >= target) {
                len = Math.min(len, right - left + 1);
                sum -= nums[left];//更新值
                left++;//出窗口
            }
            right++;
        }
        if (len == Integer.MAX_VALUE) {
            //针对示例3:target = 11, nums = [1,1,1,1,1,1,1,1]的情况
            return 0;
        }
        return len;
    }


    /**
     * 2. 无重复字符的最长子串
     * https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();//把字符串转换成字符数组
        int left = 0, right = 0;
        int ret = 0;
        int[] hash = new int[128];//构造哈希表
        while (right < s.length()) {
            //进窗口,让字符进入哈希表,也就是让对应的字符的ASCII码值作为下标,对应的hash值+1
            hash[chars[right]]++;
            //判断,如果hash[chars[right]] > 1,说明出现重复字符(left位置的字符重复了)
            while (hash[chars[right]] > 1) {
                //出窗口->从哈希表中删除该字符
                hash[chars[left]]--;
                left++;
            }
            //判断结束更新结果
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }

    /**
     * 最大连续1的个数
     * https://leetcode.cn/problems/max-consecutive-ones-iii/description/
     *
     * @param nums
     * @param k
     * @return
     */

    public int longestOnes(int[] nums, int k) {
        //问题转换:找出最长的子数组,0的个数不超过k个
        //滑动窗口
        int ret = 0;
        int left = 0, right = 0, count = 0;
        while (right < nums.length) {
            //进窗口
            if (nums[right] == 0) {
                count++;
            }
            //循环判断
            while (count > k) {
                if (nums[left] == 0) {
                    //出窗口
                    count--;
                }
                left++;
            }
            //循环结束,此时的窗口才是合法区域,才要更新结果
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }

    /**
     * 将 x 减到 0 的最小操作数
     * https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/
     *
     * @param nums
     * @param x
     * @return
     */
    public int minOperations(int[] nums, int x) {
        // 问题转换:找出最长的子数组的长度,所有的元素和刚好等于sum-x
        int sum = 0;
        int left = 0, right = 0;

        for (int num : nums) {
            sum += num;
        }


        int len = -1;
        int target = sum - x;// 找出最长的子数组的长度len,让这个子数组的元素和正好等于target
        int retSum = 0;
        while (right < nums.length) {

            // 进窗口
            retSum += nums[right];

            // 判断,根据判断结果来决定是否出窗口
            while (retSum > target && left < nums.length) {
                // 出窗口
                retSum -= nums[left];
                left++;
            }
            // 更新结果
            if (retSum == target) {
                len = Math.max(len, right - left + 1);
            }
            right++;
        }
        if (len == -1) {
            return -1;
        }
        return nums.length - len;
    }


    /**
     * 水果成篮
     * https://leetcode.cn/problems/fruit-into-baskets/description/
     *
     * @param fruits
     * @return
     */
    public int totalFruit(int[] fruits) {
        //问题转换: 找出一个最长的连续的子数组的长度,子数组中的水果种类不超过2
//        int left = 0, right = 0;
//        int ret = 0;//可以采摘的树的数量
//
//        Map<Integer, Integer> map = new HashMap<>();//key:水果种类,value:出现的次数
//
//        while (right < fruits.length) {
//            //进窗口
//            int in = fruits[right];
//            map.put(in, map.getOrDefault(in, 0) + 1);//进窗口,如果第一次进窗口那就为0,否则+1
//
//            //判断
//            while (map.size() > 2) {//如果次数>2
//
//                //出窗口
//                int out = fruits[left];
//                map.put(out, map.get(out) - 1);
//
//                if (map.get(out) == 0) {
//                    //从哈希表中删除
//                    map.remove(out);
//                }
//                left++;//出完窗口left向后移动
//            }
//            //更新结果
//            ret = Math.max(ret, right - left + 1);
//            right++;
//        }
        int left = 0, right = 0;
        int ret = 0;//可以采摘的树的数量
        int n = fruits.length;


        int[] map = new int[n + 1];//模拟哈希表
        int kinds = 0;


        while (right < n) {
            //进窗口
            int in = fruits[right];
            if (map[in] == 0) {
                kinds++;//种类+1
            }
            map[in]++;//进窗口
            //判断
            while (kinds > 2) {//如果次数>2
                //出窗口
                int out = fruits[left];
                map[out]--;
                if (map[out] == 0) {
                    //从哈希表中删除
                    kinds--;
                }
                left++;//出完窗口left向后移动
            }
            //更新结果
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }

    /**
     * 找到字符串中所有字⺟异位词
     * https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/
     *
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        //哈希表长度26->题目说明了只有小写字母
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];//p的哈希表
        for (int i = 0; i < p.length(); i++) {
            char ch = p.charAt(i);
            hash2[ch - 'a']++;//a->0,b->1,c->2.........
        }
        //双指针
        int left = 0, right = 0;
        while (right < s.length()) {
            //进窗口
            char in = s.charAt(right);
            hash1[in - 'a']++;
            //判断
            if (right - left + 1 > p.length()) {
                //需要出窗口
                char out = s.charAt(left);
                hash1[out - 'a']--;
                left++;
            }

            //更新结果,比较hash1和hash2的结果
            int count = 0;//不符合的次数
            for (int i = 0; i < 26; i++) {
                if (hash1[i] != hash2[i]) {
                    count++;
                }
            }
            //如果count==0-->两个哈希表中字符信息全部符合
            if (count == 0) {
                ret.add(left);
            }
            right++;
        }
        return ret;
    }

    //优化
    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        //哈希表长度26->题目说明了只有小写字母
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];//p的哈希表
        for (int i = 0; i < p.length(); i++) {
            char ch = p.charAt(i);
            hash2[ch - 'a']++;//a->0,b->1,c->2.........
        }
        //双指针
        int left = 0, right = 0;
        int count = 0;//统计窗口中有效字符的个数
        while (right < s.length()) {
            //进窗口
            char in = s.charAt(right);
            hash1[in - 'a']++;
            if (hash1[in - 'a'] <= hash2[in - 'a']) {
                count++;
            }

            //判断
            if (right - left + 1 > p.length()) {
                //需要出窗口
                char out = s.charAt(left);
                if (hash1[out - 'a'] <= hash2[out - 'a']) {
                    count--;
                }
                hash1[out - 'a']--;
                left++;
            }
            if (count == p.length()) {
                ret.add(left);
            }
            right++;
        }
        return ret;
    }

    /**
     * https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
     *
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring(String s, String[] words) {
        HashMap<String, Integer> hash2 = new HashMap<>();//统计words中的
        List<Integer> ret = new ArrayList<>();
        //words
        for (int i = 0; i < words.length; i++) {
            hash2.put(words[i], hash2.getOrDefault(words[i], 0) + 1);
        }
        //滑动窗口启动!
        int len = words[0].length();//
        for (int window = 0; window < len; window++) {
            int left = window, right = window;
            int count = 0;//统计有效字符串的个数
            HashMap<String, Integer> hash1 = new HashMap<>();
            while (right + len <= s.length()) {
                //进窗口
                String in = s.substring(right, right + len);
                hash1.put(in, hash1.getOrDefault(in, 0) + 1);

                if (hash1.get(in) <= hash2.getOrDefault(in, 0)) {
                    //hash2.getOrDefault-->有可能hash2中没有hash1的内容
                    count++;
                }
                //判断
                if (right - left + 1 > len * words.length) {
                    //需要出窗口
                    String out = s.substring(left, left + len);
                    if (hash1.get(out) <= hash2.getOrDefault(out, 0)) {
                        //hash2.getOrDefault-->有可能hash2中没有hash1的内容
                        count--;
                    }
                    hash1.put(out, hash1.get(out) - 1);
                    left += len;
                }
                //更新结果,比较hash1和hash2
                if (count == words.length) {
                    ret.add(left);
                }
                right += len;
            }
        }
        return ret;
    }


    /**
     * 最小覆盖子串
     * https://leetcode.cn/problems/minimum-window-substring/
     *
     * @param ss
     * @param tt
     * @return
     */
    public String minWindow(String ss, String tt) {
        //数组模拟哈希表
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];//保存t的频次


        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        int count = 0;//t字符串中字符种类个数
        //先把t的频次保存
        for (char ch : t) {
            if (hash2[ch] == 0) {
                count++;//统计tt的字符种类
            }
            hash2[ch]++;
        }

        //滑动窗口启动
        int left = 0, right = 0, kinds = 0;
        int minLen = Integer.MAX_VALUE, begin = -1;
        while (right < s.length) {
            //进窗口
            char in = s[right];
            hash1[in]++;
            //维护有效字符种类
            if (hash1[in] == hash2[in]) {
                kinds++;
            }

            //判断如果kinds==count,也就是说hash1有效字符种类和hash2一样
            while (kinds == count) {
                //更新结果,起始位置和最短长度
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    begin = left;
                }

                //出窗口
                char out = s[left];
                //出之前判断有效字符种类
                if (hash1[out] == hash2[out]) {
                    kinds--;
                }
                hash1[out]--;
                left++;
            }
            right++;
        }
        if (begin == -1) {
            return new String();
        }
        return ss.substring(begin, begin + minLen);
    }

}